Populations of vector-borne pathogens are shaped by the distribution and movement of vector and reservoir hosts. To study what impact host and vector association have on tick-borne pathogens, we investigated the population structure of Borrelia lusitaniae using multilocus sequence typing (MLST). Novel sequences were acquired from questing ticks collected in multiple North African and European locations and were supplemented by publicly available sequences at the Borrelia Pubmlst database (accessed on 11 February 2020). Population structure of B. lusitaniae was inferred using clustering and network analyses. Maximum likelihood phylogenies for two molecular tick markers (the mitochondrial 16S rRNA locus and a nuclear locus, Tick-receptor of outer surface protein A, trospA) were used to confirm the morphological species identification of collected ticks. Our results confirmed that B. lusitaniae does indeed form two distinguishable populations: one containing mostly European samples and the other mostly Portuguese and North African samples. Of interest, Portuguese samples clustered largely based on being from north (European) or south (North African) of the river Targus. As two different Ixodes species (i.e., I. ricinus and I. inopinatus) may vector Borrelia in these regions, reference samples were included for I. inopinatus but did not form monophyletic clades in either tree, suggesting some misidentification. Even so, the trospA phylogeny showed a monophyletic clade containing tick samples from Northern Africa and Portugal south of the river Tagus suggesting a population division in Ixodes on this locus. The pattern mirrored the clustering of B. lusitaniae samples, suggesting a potential co-evolution between tick and Borrelia populations that deserve further investigation.